Online scheduling of parallel jobs on two machines is 2-competitive

摘要

We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with $m$ machines, we derive lower bounds using an ILP formulation.